#include <iostream>
#include <cstdlib>
#include <ctime>
#include "xzlib.h"
#include "xstdio.h"

template<typename T>
class MergeSort
    {
    public:
	typedef int (*compare_function_t) (const T *, const T *,const void* userData);
	std::size_t buffer_capacity;
	compare_function_t comparator;

	MergeSort(compare_function_t comparator);
	void sort(const char *filename,const char* fileout, void* userData);
    };


template<typename T>
MergeSort<T>::MergeSort(compare_function_t comparator):
	buffer_capacity(1000000),
	comparator(comparator)
    {
    if(comparator==NULL)
	{
	std::cerr << "comparator is null " << std::endl;
	std::exit(EXIT_FAILURE);
	}
    }

template<typename T>
void MergeSort<T>::sort(const char *filename,const char* fileout, void* userData)
    {
    size_t buffer_size=0;
    FILE* prev_file=NULL;
    size_t items_on_file=0L;
    T *buffer=(T*)safeMalloc(buffer_capacity*sizeof(T));
    T* fileItem=(T*)safeMalloc(sizeof(T));
    //open original file
    gzFile in=safeGZOpen(filename,"rb");
    while(!gzeof(in))
	{
	std::clock_t now=std::clock();
	buffer_size=0;
	while(!gzeof(in) && buffer_size<buffer_capacity)
	    {
	    int nRead=gzread(in,&buffer[buffer_size],sizeof(T));
	    if(nRead!=sizeof(T)) break;
	    ++buffer_size;
	    }
	if(buffer_size==0) break;
	//std::cerr << "sorting buffer (n="<< buffer_size<<")" << std::endl;
	qsort_r(buffer,
		buffer_size,sizeof(T),
		(int (*)(const void*, const void*, void*))comparator,
		userData
		);
	//std::cerr << "end sorting" << std::endl;
	if(prev_file==NULL)
	    {
	    std::cerr << "dump empty buffer n="<< buffer_size <<  std::endl;
	    prev_file=safeTmpFile();
	    safeFWrite(buffer,sizeof(T),buffer_size,prev_file);
	    safeFFlush(prev_file);
	    items_on_file=buffer_size;
	    }
	else
	    {

	    //std::cerr << "merge sort *********************" <<  std::endl;
	    FILE* next_file=safeTmpFile();
	    size_t index_buffer=0;
	    size_t index_file=0;
	    bool need_read_file_item=true;

	    //std::cerr << "items_on_file " << items_on_file <<  std::endl;
	    //rewind prev_file
	    safeFSeek(prev_file,0L,SEEK_SET);
	    while(index_buffer < buffer_size && index_file<items_on_file)
		{
		if(need_read_file_item)
		    {
		    safeFRead(fileItem,sizeof(T),1,prev_file);
		    need_read_file_item=false;
		    }
		if(comparator(&buffer[index_buffer],fileItem,userData) <=0)
		    {
		    safeFWrite(&buffer[index_buffer],sizeof(T),1,next_file);
		    ++index_buffer;
		    }
		else
		    {
		    safeFWrite(fileItem,sizeof(T),1,next_file);
		    ++index_file;
		    need_read_file_item=true;
		    }
		}
	    while(index_buffer < buffer_size)
		{
		safeFWrite(&buffer[index_buffer],sizeof(T),1,next_file);
		++index_buffer;
		}
	    if(index_file< items_on_file)
		{
		safeFSeek(prev_file,sizeof(T)*index_file,SEEK_SET);
		while(index_file < items_on_file)
		    {
		    safeFRead(fileItem,sizeof(T),1,prev_file);
		    safeFWrite(fileItem,sizeof(T),1,next_file);
		    ++index_file;
		    }
		}

	    items_on_file+=buffer_size;
	    FILE* old=prev_file;
	    fclose(old);
	    std::cerr << items_on_file << " items sorted on disk" << std::endl;
	    prev_file=next_file;
	    }
	std::cerr << "time " << ((std::clock() - now)/CLOCKS_PER_SEC) << " secs" <<std::endl;
	}
    gzclose(in);
    std::cerr << "we're done saving to disk" << std::endl;
    FILE* saveAs=safeFOpen(fileout,"wb");
    if(prev_file!=NULL)
	{
	safeFSeek(prev_file,0L,SEEK_SET);
	for(std::size_t i=0;i < items_on_file;++i)
	    {
	    safeFRead(fileItem,sizeof(T),1,prev_file);
	    safeFWrite(fileItem,sizeof(T),1,saveAs);
	    }
	fclose(prev_file);
	}
    safeFFlush(saveAs);
    fclose(saveAs);
    if(fileItem!=NULL) free(fileItem);
    if(buffer!=NULL) free(buffer);
    std::cerr << "end of merge" << std::endl;
    }
